We propose a simple projection and rescaling algorithm to solve thefeasibility problem \[ \text{ find } x \in L \cap \Omega, \] where $L$ and$\Omega$ are respectively a linear subspace and the interior of a symmetriccone in a finite-dimensional vector space $V$. This projection and rescaling algorithm is inspired by previous work onrescaled versions of the perceptron algorithm and by Chubanov'sprojection-based method for linear feasibility problems. As in thesepredecessors, each main iteration of our algorithm contains two steps: a {\embasic procedure} and a {\em rescaling} step. When $L \cap \Omega \ne\emptyset$, the projection and rescaling algorithm finds a point $x \in L \cap\Omega$ in at most $O(\log(1/\delta(L \cap \Omega)))$ iterations, where$\delta(L \cap \Omega) \in (0,1]$ is a measure of the most interior point in $L\cap \Omega$. The ideal value $\delta(L\cap \Omega) = 1$ is attained when $L\cap \Omega$ contains the center of the symmetric cone $\Omega$. We describe several possible implementations for the basic procedureincluding a perceptron scheme and a smooth perceptron scheme. The perceptronscheme requires $O(r^4)$ perceptron updates and the smooth perceptron schemerequires $O(r^2)$ smooth perceptron updates, where $r$ stands for the Jordanalgebra rank of $V$.
展开▼
机译：我们提出一种简单的投影和缩放算法，以解决可行性问题\ [\ text {find} x \ in L \ cap \ Omega，\]其中$ L $和$ \ Omega $分别是线性子空间和对称圆锥的内部在有限维向量空间$ V $中。这种投影和重新缩放算法的灵感来自先前在感知器算法的重新缩放版本上的工作，以及基于Chubanov基于线性投影的问题的基于投影的方法。与这些前辈一样，我们算法的每个主要迭代都包含两个步骤：{\ embasic过程}和{\ em rescaling}步骤。当$ L \ cap \ Omega \ ne \ emptyset $时，投影和缩放算法在L \ cap \ Omega $中找到一个点$ x \至多$ O（\ log（1 / \ delta（L \ cap \ Omega ）））$迭代，其中$ \ delta（L \ cap \ Omega）\ in（0,1] $是$ L \ cap \ Omega $中最内部点的度量。理想值$ \ delta（L当\ L \ cap \ Omega $包含对称圆锥$ \ Omega $的中心时，获得\ cap \ Omega）= 1 $我们描述了基本过程的几种可能实现，包括感知器方案和平滑感知器方案。需要$ O（r ^ 4）$个感知器更新，而平滑感知器方案则需要$ O（r ^ 2）$个平滑感知器更新，其中$ r $表示约旦代数等级$ V $。
展开▼
